生命的算法复杂度：为什么进化总能找到一条简单路径？
一个问题备选解决方案数不胜数，但大多数路径可能都是死胡同。然而，进化可能已经找到了提高成功几率的方法。| 来源：Ricardo Bessa
计算机科学家向进化生物学寻求灵感，希望从天文数字般巨大的可能性集合中找到最优解。
编译：集智俱乐部翻译组
来源：quantamagazine
原题：Mathematical Simplicity May Drive Evolution’s Speed
目的论者坚持认为——进化必须以正确的顺序组装300个才能产生仅仅一个中等大小的人类蛋白质。每个位置的的有20种可能，似乎需要筛选超过20的300次方种可能性，甚至远超可观察宇宙中的原子数量。即使我们排除掉那些效用等同的冗余序列，哪怕在数十亿年内，进化通过随机突变（mutation）偶然发现正确组合也是不可能的。
他们论证中的致命缺陷是，进化不仅仅是随机测试序列，因为自然选择筛选了进化方向。此外，似乎大自然在某种程度上也找到了其他捷径，缩小广阔的可能性空间，得到可探索的、更可能产生有用解决方案的子集。
计算机科学家面临着类似的挑战，其中包括在天文数字般巨大的可能性范围中寻找最佳解决方案。有些人向生物学寻求灵感——即使生物学家也在试图弄清楚生命究竟是如何找到“最优解”的。
遗传编程（genentic programming）
几十年来流行的遗传算法（Genetic algorithms ）和优化方法（Optimization method）根据自然选择原则来策划新设计（关于机器人、药物和运输系统等），训练神经网络或加密解密数据。首先，该技术将问题的随机解决方案视为“有机体”，代码中“遗传”了某些特征或元素。这些解决方案并非完美，但是通过随机突变的组合产生第二代生物，反过来测试它们在特定任务中的“适应性”。最终，多次重复这个过程会得到高度符合的个体或解决方案。
译注：
随机突变组合有时是模仿基因改组过程的其他变化。
一些专家发展了这种方法，即所谓的遗传编程（genentic programming），开发能够编写程序并提出有效解决方案的软件（这里的“基因”可能是编程指令）。虽然事实证明，这一目标目前还不能实现，因为研究人员不得不考虑具体的数据类型和结构，以及其他条件。
不过有趣的是，这些基于进化的思维方式与数学理论遥相呼应，而数学理论很大程度上也在生物学和计算机科学的交界边缘盘旋。最近，一些科学家试图借此深入了解生物和人造物如何高效进化、创造、并学会学习。关键在于复杂度、随机性和信息的具体概念，但这些概念直到现在还没有太多实际应用。
键盘上的猴子
来源：imgflip.com
该理论发展于20世纪60年代，涉及所谓的算法信息论（algorithmic information）。首先，它以一种直观的方式考虑概率和复杂度：至少对于某些输出，在计算上更容易描述生成它的程序，而不它本身。以猴子在电脑上随意按键为例，键入圆周率的前15,000位数字的可能性极其微小——随着所需数字位数的增长，可能性会呈指数级下降。
但是，如果猴子的击键被解释为随机编写的用于生成圆周率的计算机程序，则成功的几率或“算法概率”（algorithmic probability）会显着提高。例如，用编程语言C生成圆周率的前15,000位数，代码可以短至133个字符。
换句话说，算法信息理论指的是，因为描述某些类型的输出的程序很短，相比随机生成输出本身，随机生成描述它的程序的可能性要大得多。通过这种方式，更容易随机生成诸如分形这类复杂结构。
但是数学家们很快发现了这种方法的问题：无法计算给定输出的算法复杂度（Kolmogorov复杂度），即无法计算生成输出所需的最短程序的长度。因此，计算机科学家无法确定压缩弦或其他物体的理想方法。
曾任职于IBM Thomas J. Watson中心和里约热内卢联邦大学（Federal University of Rio de Jeiro）的著名数学家Gregory Chaitin是算法信息理论的创始人之一，他认为进化论可以被理解为一种遍历软件空间的随机计算路径。
因此，算法信息理论主要归结为纯数学领域，用于探索相关定理并定义随机性和结构，实际应用似乎遥不可及。该理论的另一位创始人著名数学家Gregory Chaitin表示：“在数学上，它是一种简洁而优雅的复杂度衡量标准，可惜它的实际应用看起来遥遥无期。”
但这并没有阻止他进行尝试。2012年，他出版了一本书，描述道如果将生命史比作软件设计，那么进化就是在巨大的可能性空间里探索。变动的突变并不遵循统计上随机的概率分布，而是遵循基于Kolmogorov复杂度的分布。但他还无法验证这个猜想。
书名：
证明达尔文：进化和生物创造性的一个数学理论
（Proving Darwin: Making Biology Mathematical）
目前，一些科学家希望通过结合生物和计算机科学来重振这一理论。
进化对“简单性”的追求
瑞典卡罗林斯卡研究所的计算机科学家Hector Zenil是试图重振该理论的人之一。他一直在与其他研究人员合作，将Kolmogorov复杂度作为分析生物网络复杂度的指标，例如细胞中典型的基因调控或蛋白质相互作用。研究人员估算网络的算法信息内容，然后向网络引入涨落并测试对Kolmogorov复杂度的影响。他们希望这种方法能够揭示网络中各种元素的相对重要性，以及网络如何应对变化、调整功能。
瑞典卡罗林斯卡研究所的计算机科学家Hector Zenil试图根据算法复杂度分析演化着的生物网络。
发表在arxiv.org上的一项最新的研究成果表示，他们发现，通过引入突变来延长网络的描述性程序，增加了网络的Kolmogorov复杂度，系统对扰动更加敏感，因此倾向于增加系统可运行的功能。如果他们令网络走向简单，那么这些功能就会减少，但同时功能也会更加稳定。
论文题目：
An Algorithmic Information Calculus for Causal Discovery and Reprogramming Systems
论文地址：
https://arxiv.org/abs/1709.05429
但是，Kolmogorov复杂度是否可以不仅仅作为一种工具，还成为Chaitin认为的变革的驱动力量？这一点还有待观察。尽管存在问题，算法信息已在生物学领域具有一定吸引力。传统上，用于描述进化动力学（evolutionary dynamics）的数学框架是群体遗传学（populations），关于基因出现在群体中的可能频率的统计模型。但是，群体遗传学存在局限性，例如，它不能解释生命起源和其他主要的生物学转变，也不能解释全新基因的出现。
Chaitin说：“生物创造力（biological creativity）这一概念便迷失在这种可爱的数学理论中。”但是，如果我们用算法信息来解释：“创造力就自然而然地显现了。”
群体遗传学 | 来源：Ralf Sommer
类似的现象如，‘进化过程随时间的推移，不断改进自身，变得更有效率’。英国赫特福德大学（University of Hertfordshire）的计算机科学家兼人工智能教授丹尼尔•波拉尼（Diel Poli）说：“我非常确信进化可以自我学习。如果算法复杂度渐近下降，我并不会感到惊讶。”
Zenil和他的团队着手试验性地探索算法复杂度框架的生物学和计算机科学含义。他们采用所开发的复杂度近似技术（approximating complexity framework，此前用于分析和扰乱网络），通过控制突变偏向较低算法复杂度的矩阵（由1和0组成，代表基因之间的相互作用），将人工遗传网络朝着某些目标“演化”。换句话说，他们选择了更宏观的结构。
他们指出，与统计学上的随机涨落相比，这种突变偏差让网络更快地朝着解决方案演化。也出现了其他特征，包括稳定而规则的结构，矩阵内的部分已经简单到了新一代也不太可能改进的程度。
Zenil说：“一些区域更容易，或者更不容易产生突变，仅仅是因为它们可能已经进化到了一定程度的简单性。这看起来就像基因一样。”遗传记忆反过来快速产生了更大的结构，研究人员提出，这意味着算法上可能的突变也会导致多样性爆炸和灭绝。
“这意味着，当我们谈论进化时，考虑计算过程是富有成效的。”他希望利用对随机性和复杂性的理解，识别更容易产生突变的路径，或者弄清楚为什么某些遗传的相互作用可能与癌症等疾病有关。
生命是演化中的软件？
Zenil希望探索生物进化是否按照相同的计算规则运作，但大多数专家对此都有疑虑。目前尚不清楚哪种自然机制影响近似算法复杂度（approximating ic complexity），或使这种突变偏差起作用。此外，法国国家科学研究中心的数学家朱塞佩·隆戈（Giuseppe Longo）说：“认为生命（life）用四个字母可以完全编码的想法是错误的。DNA非常重要，但如果不在细胞内、在生物体内、在生态系统中，它就意义全无。”其他的相互作用同样起作用，算法信息的应用无法捕捉到这种过程的复杂程度。
尽管如此，这个概念仍引起了人们的兴趣，特别是这种思考进化的方式和计算过程似乎有一些共同点：至少在主题上，遗传编程的目标是进化软件。
事实上，Chaitin和Zenil关于Kolmogorov复杂度和遗传编程方法的想法之间存在着一些有趣的暗示。例如，在2001年，一组研究人员报告说，遗传程序输出的复杂度可能受到原始程序的Kolmogorov复杂度的限制。
论文题目：
Computational Complexity, Genetic Programming, and Implications
论文地址：
https://link.springer.com/chapter/10.1007/3-540-45355-5_28
但在大多数情况下，Kolmogorov的复杂度并没有帮助计算机科学家理解这些想法。相反，他们尝试了其他方法来调节所涉及的遗传和突变。一些团体直接调整了突变率; 其他人则偏向于调整系统，支持取代更大块代码的突变。
马萨诸塞州汉普郡学院的计算机科学家Lee Spector说：“人们已经提出了数十种，甚至数百种不同版本的突变和交叉，” Spector最近领导了一个团队，展现在整个生物体的基因组中添加和删除突变相比直接替换基因的优势。这种新型遗传算子（genentic operator）最终以指数形式扩展了基因组搜索空间的路径数量，带来了更好的解决方案。
汉普郡学院计算机科学家Lee Spector，希望通过开发新的遗传编程技术，大大提高人工智能的潜力。
也就是说，许多研究人员走向了相反的方向，寻求加快缩小搜索空间的过程的方法，而不是限制搜索空间以至于错过了最优解。一种方法是简单性：正如Eugene Wigner在1960年指出 “数学在自然科学中不合理的有效性”——计算机科学家发现，简洁而优雅的模型往往被证明有更大的适用范围和效度。Spector说：“问题是，它是否在向我们揭示宇宙的某些深刻信息？无论如何，它看起来有用吗？”
他还警告说，简化演变程序具有破坏性，例如，奖励较短的程序会裁掉可能对后代有益的基因（即使目前看来是垃圾基因），牺牲了演化过程中的可能的最优解。他说：“所以你们将被困住。”
但简单性仍然是一个诱人的目标，也被证明是有用的。在去年发表的成果中，Spector和他的同事们发现，在执行基因编程技术后，如果程序大小缩减到原始的25％，能够更好地处理新数据，并且可以用于更广泛的一般问题。
论文题目：
Improving generalization of evolved programs through automatic simplification
论文地址：
https://dl.acm.org/citation.cfm?id=3071178.3071330
这是他一直关注算法信息理论的研究成果的部分原因，尽管他说他还没有确切地看到它将如何影响这个领域。
从自然中学习
也许Zenil的团队迈出了实现这种影响的第一步，但为了使他们的研究的应用更加普遍、实际，他们必须在其他类型的搜索问题上测试他们的方法。
理论神经科学家拉里萨·阿尔巴塔基斯（Larissa Albtakis）表示，他们还通过限制他们必须遍历的搜索空间来加速遗传算法：“他们在基于结构的限制方面有一个很好的观点。在许多方面，自然是结构化的，如果以此为原点，那么尝试所有可能的一致化的突变是一种愚蠢的行为。”
威斯康星大学麦迪逊分校的理论神经科学家拉里萨·阿尔巴塔基斯（Larissa Albtakis）
她补充说：“任何对我们来说有意义的东西都是以某种特定结构构建的。”
虽然Spector仍然怀疑Zenil最近研究的应用是否超出了他所探讨的非常具体的问题：“这里的概念背后的信息理论很有趣，而且可能非常重要。我觉得这很令人兴奋，它似乎来自另一个星球。也许我们社区中的人们都没有意识到这些见解。毕竟，算法信息涉及了一些遗传编程专家都可能无法融入到研究里的各种概念，包括进化的开放性。”
Spector说：“我非常清楚它的重要性，即便如此，他们正在研究的和实际应用之间仍然存在很大差距。”Chaitin表示，“将生命视为演化中的软件”是极有价值的，尽管判断其价值可能为时过早。无论是考虑人造物还是生物体，看看我们能走多远吧。
翻译：杨清怡
审校：李周园
编辑：王怡蔺
原文：
https://www.quantamagazine.org/computer-science-and-biology-explore-algorithmic-evolution-20181129/
推荐阅读
推荐课程
PC观看地址：
https://campus.swarma.org/gpac=123
集智俱乐部QQ群｜877391004
商务合作及投稿转载｜swarma@swarma.org
◆ ◆ ◆
搜索公众号：集智俱乐部
加入“没有围墙的研究所”
让苹果砸得更猛烈些吧！